package 我的Java学习_算法基础.day_07;

/**
 * @author 挚爱之夕
 * @date 2021/8/19 - 08 - 19 - 14:58
 * @Description: 我的暑假Java学习.day_06
 * @Version: 1.0
 */

/**
 * 有一个x*y的网格，一个机器人只能走格点且只能向右或向下，要从左上角走到右下角。
 *
 * 设计一个算法，计算机器人有多少种走法。
 *
 * 给定两个正整数int x, int y,返回机器人的走法 数目，保证x+y小于等于12
 */
public class _106_机器人走方格问题 {
    public static void main(String[] args) {
        long now = System.currentTimeMillis();
        System.out.println(f(15,15));
        System.out.println(System.currentTimeMillis()-now);
        now = System.currentTimeMillis();
        System.out.println(f1(30,30));
        System.out.println(System.currentTimeMillis()-now);
    }
    //递归,效率低，简洁
    private static int f(int x,int y){
        if(x==1||y==1){
            return 1;
        }
        return f(x-1,y)+f(x,y-1);
    }
    //递推，效率高
    private static int f1(int m,int n){
        int[][] state = new int[m+1][n+1];
        for(int i=1;i<=n;i++){
            state[i][1]=1;
        }
        for(int i=1;i<=n;i++){
            state[1][i]=1;
        }
        for(int i =2;i<=m;i++){
            for(int j =2;j<=n;j++){
                state[i][j]=state[i][j-1]+state[i-1][j];
            }
        }
        return state[m][n];
    }
}
